package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1728 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
            int rows = grid.length, cols = grid[0].length();
            int catX = -1, catY = -1, mouseX = -1, mouseY = -1, foodX = -1, foodY = -1;
            char[][] map = new char[rows][cols];
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    char cur = grid[r].charAt(c);
                    if (cur == 'C') {
                        catX = r;
                        catY = c;
                    } else if (cur == 'M') {
                        mouseX = r;
                        mouseY = c;
                    } else if (cur == 'F') {
                        foodX = r;
                        foodY = c;
                    } else if (cur == '#') {
                        map[r][c] = '#';
                    }
                }
            }
            Boolean[][][][][] cache = new Boolean[rows][cols][rows][cols][2010];
            boolean res = miniMax(catX, catY, mouseX, mouseY, 0, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
            return res;
        }

        private boolean miniMax(int catX, int catY, int mouseX, int mouseY, int move, Boolean[][][][][] cache,
                                int catJump, int mouseJump, int foodX, int foodY, int rows, int cols, char[][] map) {
            //already known
            if (cache[catX][catY][mouseX][mouseY][move] != null) {
                return cache[catX][catY][mouseX][mouseY][move];
            }
            //termination
            Boolean res = null;
            if (catX == mouseX && catY == mouseY) res = false;
            if (catX == foodX && catY == foodY) res = false;
            if (mouseX == foodX && mouseY == foodY) res = true;
            if (move > 2000) res = false;
            if (res != null) {
                cache[catX][catY][mouseX][mouseY][move] = res;
                return res;
            }
            //miniMax algorithm
            if (move % 2 == 0) { //mouse turn, any true is true, all false is false
                boolean tmp = false;
                //go through all choices
                //stay
                tmp |= miniMax(catX, catY, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                if (tmp == true) {
                    cache[catX][catY][mouseX][mouseY][move] = true;
                    return true;
                }
                //left
                for (int j = 1; j <= mouseJump; j++) {
                    int myy = mouseY - j;
                    if (myy < 0 || map[mouseX][myy] == '#') break;
                    tmp |= miniMax(catX, catY, mouseX, myy, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == true) {
                        cache[catX][catY][mouseX][mouseY][move] = true;
                        return true;
                    }
                }
                //right
                for (int j = 1; j <= mouseJump; j++) {
                    int myy = mouseY + j;
                    if (myy >= cols || map[mouseX][myy] == '#') break;
                    tmp |= miniMax(catX, catY, mouseX, myy, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == true) {
                        cache[catX][catY][mouseX][mouseY][move] = true;
                        return true;
                    }
                }
                //up
                for (int j = 1; j <= mouseJump; j++) {
                    int mxx = mouseX - j;
                    if (mxx < 0 || map[mxx][mouseY] == '#') break;
                    tmp |= miniMax(catX, catY, mxx, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == true) {
                        cache[catX][catY][mouseX][mouseY][move] = true;
                        return true;
                    }
                }
                //down
                for (int j = 1; j <= mouseJump; j++) {
                    int mxx = mouseX + j;
                    if (mxx >= rows || map[mxx][mouseY] == '#') break;
                    tmp |= miniMax(catX, catY, mxx, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == true) {
                        cache[catX][catY][mouseX][mouseY][move] = true;
                        return true;
                    }
                }
                //final
                cache[catX][catY][mouseX][mouseY][move] = false;
                return false;
            } else { //cat turn, any false is false, all true is true
                boolean tmp = true;
                //go through all choices
                //stay
                tmp &= miniMax(catX, catY, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                if (tmp == false) {
                    cache[catX][catY][mouseX][mouseY][move] = false;
                    return false;
                }
                //left
                for (int j = 1; j <= catJump; j++) {
                    int cyy = catY - j;
                    if (cyy < 0 || map[catX][cyy] == '#') break;
                    tmp &= miniMax(catX, cyy, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == false) {
                        cache[catX][catY][mouseX][mouseY][move] = false;
                        return false;
                    }
                }
                //right
                for (int j = 1; j <= catJump; j++) {
                    int cyy = catY + j;
                    if (cyy >= cols || map[catX][cyy] == '#') break;
                    tmp &= miniMax(catX, cyy, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == false) {
                        cache[catX][catY][mouseX][mouseY][move] = false;
                        return false;
                    }
                }
                //up
                for (int j = 1; j <= catJump; j++) {
                    int cxx = catX - j;
                    if (cxx < 0 || map[cxx][catY] == '#') break;
                    tmp &= miniMax(cxx, catY, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == false) {
                        cache[catX][catY][mouseX][mouseY][move] = false;
                        return false;
                    }
                }
                //down
                for (int j = 1; j <= catJump; j++) {
                    int cxx = catX + j;
                    if (cxx >= rows || map[cxx][catY] == '#') break;
                    tmp &= miniMax(cxx, catY, mouseX, mouseY, move + 1, cache, catJump, mouseJump, foodX, foodY, rows, cols, map);
                    if (tmp == false) {
                        cache[catX][catY][mouseX][mouseY][move] = false;
                        return false;
                    }
                }
                //final
                cache[catX][catY][mouseX][mouseY][move] = true;
                return true;
            }
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC1728 an = new LC1728();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
